#include <iostream>
#include <vector>
#include <numeric>
#include <list>
#include <utility>
#include <cassert>

static void compute_phi(int N, std::vector<int> &phi)
{
	assert(phi.size() == N+1);

	for (int n = 0; n <= N; n++)
	{
		phi[n] = (n % 2 == 0)? n / 2 : n;
	}
	for (int p = 3; p <= N; p += 2)
	{
		if (phi[p] == p)
		{
			for (int k = p; k <= N; k += p)
				phi[k] = phi[k] / p * (p - 1);
		}
	}
}

static int count_sequence(int N, int M, const std::vector<int> &phi)
{
	assert(phi.size() == N+1);

	std::vector<int> count(N+1);
	count[6] = 1;
	int total = 1;
	for (int n = 7; n <= N; n++)
	{
		int c = 0;
		int phi_n = phi[n];
		for (int i = phi_n + 1; i < n; i++)
		{
			if (phi[i] < phi_n)
				c = (c + count[i]) % M;
		}
		count[n] = c;
		total = (total + c) % M;
		if (n % 10000 == 0)
		{
			std::cout << "S(" << n << ") = " << total << std::endl;
		}
	}
	return total;
}

static int count_sequence2(int N, int M, const std::vector<int> &phi)
{
	// Let count[b] store the number of sequences where the first element
	// (a1, b1) satisfies a1 >= a, b1 = b.
	// As b = phi(n) is even for n >= 3, we only need to store the even
	// elements of count[b].
	std::vector<int> count((N+1)/2);

	// Work from the last element back-ward to fill the array.
	for (int a = N; a >= 6; a--)
	{
		int b = phi[a];
#if 1
		//std::cout << "Summing up range " << (b/2+1) << " till " << (a+1)/2 << std::endl;
		int sum = std::accumulate(count.cbegin()+b/2+1, count.cbegin()+(a+1)/2, 1LL) % M;
#else
		int sum = 1;
		for (int i = b/2 + 1; i < (a+1)/2; i++)
			sum = (sum + count[i]) % M;
#endif
		count[b/2] = (count[b/2] +  sum) % M;
		//if (a % 1000 == 0)
		//{
		//	std::cout << "Processing " << a << "..." << std::endl;
		//}
	}
	return count[phi[6]/2];
}

static int count_sequence3(int N, int M, const std::vector<int> &phi)
{
	// Let count[b] store the number of sequences where the first element
	// (a1, b1) satisfies a1 >= a, b1 = b.
	// As b = phi(n) is even for n >= 3, we only need to store the even
	// elements of count[b].
	struct node_t
	{
		int next;	// the next (smaller) phi value / 2
		int count;	// number of sequences starting with this phi value
	public:
		node_t() : next(0), count(0) { }
	};
	std::vector<node_t> count((N+1)/2);

	// Work from the last element back-ward to fill the array.
	for (int a = N; a >= 6; a--)
	{
		int b = phi[a];

		// Remove element e from the head of the list if phi(e) >= a.
		// Since we do this at every step, there can be at most one
		// element to remove in each step.
		if (2*count[0].next >= a)
			count[0].next = count[count[0].next].next;

		// Sum up the counters of phi between (b, a).
		long long sum = 1;
		int i = 0;
		while (count[i].next > b/2)
		{
			i = count[i].next;
			sum += count[i].count;
		}
		count[b/2].count = (count[b/2].count + sum) % M;

		// Insert b into the list if not already there.
		if (count[i].next < b/2)
		{
			count[b/2].next = count[i].next;
			count[i].next = b/2;
		}

		// Display debugging message.
		if (a % 10000 == 0)
		{
			std::cout << "Processing " << a << "..." << std::endl;
		}
	}
	return count[phi[6]/2].count;
}

void solve_problem_337()
{
#if 0
	const int N = 100;
	const int M = 1000000000;
#else
	const int N = 20000000;
	//const int N = 100000;
	const int M = 100000000;
#endif

	bool verbose = true;

	// Use a Sieve method to compute the totient function for all integers n <= N.
	if (verbose)
	{
		std::cout << "Computing phi function..." << std::endl;
	}
	std::vector<int> phi(N+1);
	compute_phi(N, phi);
	//for (int n = 1; n <= N; n++)
	//{
	//	std::cout << "(" << n << ", " << phi[n] << ")" << std::endl;
	//}

	// Count the number of conforming sequences ending with (a_n, phi(a_n)).
	if (verbose)
	{
		std::cout << "Counting sequences..." << std::endl;
	}
	int total = count_sequence3(N, M, phi);
	std::cout << "S(" << N << ") = " << total << std::endl;
}
